이진 트리 탐색 구현

📔 문제 설명

첫번째 인수 lst를 이용하여 이진 탐색 트리를 생성하고, 두번째 인수 searchList에 있는 각 노드를 이진 탐색 트리에서 찾을 수 있는지 확인하여 true또는 false를 담은 배열 result를 반환하는 함수 solution()을 작성하세요

📓 제약 조건

lst의 노드는 정수로 이루어져 있으며 1,000,000개를 초고하하지 않습니다.
이진 탐색 트리의 삽입과 탐색 기능을 구현해야 합니다.
searchList의 길이는 10이하입니다.

📓 입출력의 예

❗ 1번째

먼저 노드 클래스를 생성 그리고 이진 탐색 트리 클래스를 생성하여 알맞은 위치에 노드 클래스를 넣을수있도록 하게 설계한다 그 후에 이진탐색에 규칙에 맞게 탐색하는 메서드를작성한다.

✅ 실행 코드

class 노드 {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class 이진탐색트리 {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new 노드(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return true;
      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }
}

function solution(lst, searchList) {
  const tree = new 이진탐색트리();
  for (const num of lst) {
    tree.insert(num);
  }

  return searchList.map(num => tree.search(num));
} 

📚 문제 느낀점

문제는 코테에 자주 나오는 형식이 아니라 이전 트리 순회 문제처럼 이진 탐색이 어떤건지 알려주는 느낌의 문제였다 이렇게 자바스크립트로 작성해서 문제를 풀어보니 생각도 많아지고 어려웠던거같다.

© 문제 출처

저자 출제